package me.seu.demo.algorithms;

import java.util.Arrays;

/**
 * 堆排序
 *
 *
 * @since 2021/2/18 下午5:05
 */
public class HeapSort {


    /**
     * 堆排序(升序)
     *
     * @param array 待调整的堆
     */
    public static void heapSort(int[] array) {
        // 1.把无序数组构建成最大堆。
        for (int i = (array.length - 2) / 2; i >= 0; i--) {
            downAdjust(array, i, array.length);
        }
        System.out.println("最大堆：");
        System.out.println(Arrays.toString(array));
        System.out.println("排序后：");
        // 2.循环交换集合尾部元素到堆顶，并调节堆产生新的堆顶。
        for (int i = array.length - 1; i > 0; i--) {
            // 最后一个元素和第一元素进行交换
            int temp = array[i];
            array[i] = array[0];
            array[0] = temp;
            // 下沉调整最大堆
            downAdjust(array, 0, i);
        }
    }

    /**
     * 最大堆 下沉操作
     *
     * @param array
     * @param index
     * @param length
     */
    private static void downAdjust(int[] array, int index, int length) {
        int parent = index;
        int child = parent * 2 + 1;
        while (child < length) {
            if ((child + 1 < length) && array[child + 1] > array[child]) {
                child++;
            }
            if (array[parent] < array[child]) {
                int temp = array[parent];
                array[parent] = array[child];
                array[child] = temp;

                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }

    /**
     * 堆排序(升序)
     *
     * @param array 待调整的堆
     */
    public static void heapSortV2(int[] array) {
        // 1.把无序数组构建成最大堆。
        for (int i = (array.length - 2) / 2; i >= 0; i--) {
            downAdjustV2(array, i, array.length);
        }
        System.out.println("最大堆：");
        System.out.println(Arrays.toString(array));
        System.out.println("排序后：");
        // 2.循环交换集合尾部元素到堆顶，并调节堆产生新的堆顶。
        for (int i = array.length - 1; i > 0; i--) {
            // 最后一个元素和第一元素进行交换
            int temp = array[i];
            array[i] = array[0];
            array[0] = temp;
            // 下沉调整最大堆
            downAdjustV2(array, 0, i);
        }
    }

    /**
     * 最大堆 下沉操作
     *
     * @param array
     * @param parent
     * @param length
     */
    private static void downAdjustV2(int[] array, int parent, int length) {
        int parentTemp = array[parent];
        int child = parent * 2 + 1;
        while (child < length) {
            if ((child + 1 < length) && array[child + 1] > array[child]) {
                child++;
            }
            if (parentTemp >= array[child]) {
                break;
            }

            array[parent] = array[child];

            parent = child;
            child = parent * 2 + 1;
        }
        array[parent] = parentTemp;
    }

    /**
     * 最小堆 上浮调整
     *
     * @param array 待调整的堆
     */
    public static void upAdjust(int[] array) {
        int childIndex = array.length - 1;
        int parentIndex = (childIndex - 1) / 2;
        // temp保存插入的叶子节点值，用于最后的赋值
        int temp = array[childIndex];
        while (childIndex > 0 && temp < array[parentIndex]) {
            //无需真正交换，单向赋值即可
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = (parentIndex - 1) / 2;
        }
        array[childIndex] = temp;
    }

    /**
     * 最大堆 上浮调整
     *
     * @param arr
     */
    private static void upAdjustV2(int[] arr) {
        int length = arr.length;
        int child = length - 1;
        int parent = (child - 1) / 2;

        int temp = arr[child];
        while (child > 0) {
            if (temp <= arr[parent]) {
                break;
            } else {
                arr[child] = arr[parent];
                child = parent;
                parent = (child - 1) / 2;
            }
        }

        arr[child] = temp;
    }

    /**
     * 最大堆 上浮调整
     *
     * @param arr
     */
    private static void upAdjustV3(int[] arr) {
        int length = arr.length;
        int child = length - 1;
        int parent = (child - 1) / 2;

        int temp = arr[child];
        while (child > 0 && temp > arr[parent]) {
            arr[child] = arr[parent];
            child = parent;
            parent = (child - 1) / 2;
        }

        arr[child] = temp;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 2, 6, 5, 7, 8, 9, 10, 0};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));

        int[] arr2 = new int[]{1, 3, 2, 6, 5, 7, 8, 9, 10, 0};
        heapSortV2(arr2);
        System.out.println(Arrays.toString(arr2));
    }

}
